package algorithm.dynamic_programming;


import java.util.HashMap;

//一维线性
public class ScoreLargest {

    public static int scoreLargest(int[] arr){
        if (arr == null || arr.length < 2) {
            return -1;
        }
        HashMap<String, Integer> map = new HashMap<>();
       return process(getString(arr), map);
    }

    public static int process(String s, HashMap<String, Integer> dp){
        if(dp.containsKey(s))
            return dp.get(s);
        int[] arr = getArray(s);
        if(arr.length == 2)
            return arr[0] + arr[1];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length - 1; i++) {
            int[] newArr = new int[arr.length - 1];
            int index = i;
            int curScore = arr[i] + arr[i + 1];
            for (int j = 0; j < newArr.length; j++) {
                if(j < i)
                    newArr[j] = arr[j];
                else
                    if(j == i)
                        newArr[j] = arr[i] + arr[i + 1];
                    else
                        newArr[j] = arr[j + 1];
            }
            String rest = getString(newArr);
            max = Math.max(max, process(rest, dp) + curScore);
        }
        dp.put(s, max);
        return max;
    }

    public static String getString(int[] arr){
        StringBuffer buffer = new StringBuffer();
        int index = 0;
        for (int i = 0; i < arr.length * 2 - 1; i++) {
            if((i & 1) == 0){
                buffer.append(arr[index++]);
            }else{
                buffer.append("_");
            }
        }
        return buffer.toString();
    }

    public static int[] getArray(String s){
        String[] str = s.split("_");
        int[] arr = new int[str.length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }
        return arr;
    }

    //解法二：范围上的尝试模型
    public static int scoreLargest2(int[] arr){
        if (arr == null || arr.length < 2) {
            return -1;
        }
        int[][] dp = new int[arr.length][arr.length];
        int[] sumArr = new int[arr.length];
        sumArr[0] = arr[0];
        for (int i = 1; i < sumArr.length; i++) {
            sumArr[i] = sumArr[i - 1] + arr[i];
        }

        for (int i = 0; i < arr.length - 1; i++) {
            dp[i][i + 1] = arr[i] + arr[i + 1];
        }

        for (int i = arr.length - 3; i >= 0; i--) {
            for (int j = i + 2; j < arr.length; j++) {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]) + sumArr[j] - sumArr[i] + arr[i];
            }
        }
        return dp[0][arr.length - 1];
    }


    public static int min2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return -1;
        }
        int N = arr.length;
        int[] s = sum(arr);
        int[][] dp = new int[N][N];
        // dp[i][i] = 0
        for (int L = N - 2; L >= 0; L--) {
            for (int R = L + 1; R < N; R++) {
                int next = Integer.MIN_VALUE;
                // dp(L..leftEnd)  + dp[leftEnd+1...R]  + 累加和[L...R]
                for (int leftEnd = L; leftEnd < R; leftEnd++) {
                    next = Math.max(next, dp[L][leftEnd] + dp[leftEnd + 1][R]);
                }
                dp[L][R] = next + w(s, L, R);
            }
        }
        return dp[0][N - 1];
    }


    public static int min1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return -1;
        }
        int N = arr.length;
        int[] s = sum(arr);
        return process1(0, N - 1, s);
    }

    public static int[] sum(int[] arr) {
        int N = arr.length;
        int[] s = new int[N + 1];
        s[0] = 0;
        for (int i = 0; i < N; i++) {
            s[i + 1] = s[i] + arr[i];
        }
        return s;
    }
    public static int w(int[] s, int l, int r) {
        return s[r + 1] - s[l];
    }

    public static int process1(int L, int R, int[] s) {
        if (L == R) {
            return 0;
        }
        int next = Integer.MIN_VALUE;
        for (int leftEnd = L; leftEnd < R; leftEnd++) {
            next = Math.max(next, process1(L, leftEnd, s) + process1(leftEnd + 1, R, s));
        }
        return next + w(s, L, R);
    }


//    public static void main(String[] args) {
//        int[] arr = {108, 6, 99, 44, 9, 55, 45, 20, 1, 8, 3, 55, 10};
////        String string = getString(arr);
////        int[] array = getArray(string);
////        for (int i = 0; i < array.length; i++) {
////            System.out.println(array[i]);
////        }
//        int i = min1(arr);
//        int i1 = scoreLargest2(arr);
//        System.out.println(i);
//        System.out.println(i1);
//    }

    public static int[] randomArray(int len, int maxValue) {
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = (int) (Math.random() * maxValue);
        }
        return arr;
    }

    public static void main(String[] args) {
        int N = 15;
        int maxValue = 100;
        int testTime = 5000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int len = (int) (Math.random() * N);
            int[] arr = randomArray(len, maxValue);
            int ans1 = scoreLargest2(arr);
            int ans2 = scoreLargest(arr);
//            int ans2 = min2(arr);

            if (ans1 != ans2) {

                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束");
    }
}
